<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<!--
Design by Free CSS Templates
http://www.freecsstemplates.org
Released for free under a Creative Commons Attribution 2.5 License
-->
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>CSC560 Design and Analysis of Real-Time Systems</title>
<meta name="keywords" content="CSC560" />
<meta name="description" content="CSC560" />
<link href="../default.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="wrapper">
	<div id="header">
		<h1>CSC560</h1>
		<h2>Design and Analysis of Real-Time Systems</h2>
		<ul>
			<li class="first"> <a href="../index.html" accesskey="1" title="">Home</a> </li>
			<li> <a href="../project1/index.html" accesskey="2" title="">Project 1</a>	</li>
			<li> <a href="../project2/index.html" accesskey="3" title="">Project 2</a> </li>
			<li> <a href="index.html" accesskey="4" title=""><b>Project 3</b></a> </li>
			<li> <a href="../project4/index.html" accesskey="4" title="">Project 4</a> </li>
			<li> <a href="../project5/index.html" accesskey="4" title="">Project 5</a> </li>
		</ul>
	</div>
</div>
<div id="content">
	<div id="colOne">
		<h2>Timed Mutex</h2>
		<p>			
			The core task here is to implement a timed mutex. Unlike semaphore, a mutex supports ownership. Thus, “only the 
			owner (the task that acquires the lock) can unlock the mutex. In addition, the owner may ‘recursively’ lock the 
			same mutex multiple times and must recursively unlock it accordingly. Finally, lock on a mutex is timed, and the 
			owner must unlock the mutex before the pre-determined deadline to 
			avoid a timing violation that would result in a system abort in our implementation.
		</p>
		<h3>Requirements</h3>
		<p>
			We have implemented the following requirements:
		<table cellpadding="0" cellspacing="0" border="0">
		<thead>
			<tr>
				<th><h4>Feature Name</h4></th>
				<th><h4>Description</h4></th>
			</tr>
		</thead>
		<tbody>
			<tr>
				<td>Mutex_Init()</td>
				<td>Like Events, a mutex must be created with Mutex_Init(), which returns a newly initialized and “free” 
				(unlocked) mutex. In addition, only a limited number of mutexes may be created in the RTOS.
				</td>
			</tr>
			<br></br>
			<tr><td>==========</td><td>         </td></tr>
			<tr>
				<td>Mutex_Lock(m,t)</td>
				<td>A task may attempt to acquire the lock on a mutex, m, and to lock it up to a maximum of t ticks. 
				If the mutex is free the calling task becomes the owner. Otherwise, the calling task is blocked and 
				placed on a queue for m.
				</td>
			</tr>
			<tr><td>==========</td><td>         </td></tr>
			<tr>
				<td>Mutex_Unlock(m)</td>
				<td>Owning task of the mutex, m, must release / unlock m by calling Mutex_Unlock(m). Note that it’s a 
				timing violation if owner of m does not unlock it before the deadline, t ticks after acquiring the lock 
				on m, as constrained by t in Mutex_Lock(m,t). As a result of unlocking m, the task waiting on m the 
				longest will become the new owner of m. 
				</td>
			</tr>
		</tbody>
		</table>			
		</p>
		<br></br>
		<h3>Development Process</h3>
		<p>
			In developing Timed Mutex, we started by reading the RTOS code for events because of their similarity in 
			wait and block. Nevertheless, Timed Mutex has a few extra features than Event, for example, ownership, 
			locking, time constraint of a mutex, and promotion of owner’s scheduling level. Thus, we defined the C struct, 
			‘mutex’, in ‘kernel.h’ to store related information. A number of new RTOS runtime errors have also been added 
			to ‘error_code.h’ for mutex-related runtime errors. 
			<br>
			<br>
			<h4>Mutex_Init()</h4>
			Similar to Event, Time Mutex is implemented as an array of mutexes since no memory allocation for pointer is 
			performed in our ROTS. Thus, if not exceeding the maximum number of mutexes supported, Mutex_Init() simply 
			returns the ‘array index plus 1’ of the newly initialized mutex, as if the index was an pointer. Note the 
			plus 1 because 0 (NULL) is returned in case of unsuccessful mutex initialization.
			<br>
			<br>
			<h4>Mutex_Lock()</h4>
			The keys in mutex lock are as follows. First, there is the notion of ownership. A task becomes the owner of 
			a mutex if it’s free. Once the mutex is locked, only the owner can recursively lock the mutex. We use a counter, 
			lock_count, to keep track of the number of recursive locks on the mutex. Second, the owner is promoted to System 
			level task during the time it holds the lock on the mutex. That is, the owning task is appended to the System 
			task queue. Third, a mutex can only be locked for a specific number of ticks at one time by a task, recursively 
			locked or not. Lastly, a task blocks on the mutex if it’s not free, and the task is added to the waiting queue 
			of the mutex. 
			<br>
			<br>
			<h4>Mutex_Unlock()</h4>
			Unlocking a mutex is a bit trickier than locking. The keys in mutex unlock are as the following. First, only 
			the owner of a mutex may unlock it. It’s the application’s responsibility to ensure a mutex is unlocked in time. 
			Otherwise, it’s a RTOS timing violation. Second, when a mutex is unlock and becomes free, the owning task must 
			be restored to its original scheduling level. Lastly, to prevent barging, (See the section, Challenges.) the 
			ownership of the mutex is passed to the first task waiting on the mutex the longest without unlocking the mutex 
			and the new owner is promoted to a System task. The new owner is then unblocked and added to the System task 
			queue.
			<br>
			<br>
		</p>
		<h3>Challenges</h3>
		<p>
			In this section, we elaborate on a number of interesting challenges encountered during the development. 
			<br>
			<br>
			<h5>Timing Violation of a Locked Mutex</h5>
			We first implemented lazy check of the timing violation where only at mutex unlock did the RTOS check 
			to see whether the mutex was unlocked before the deadline. Later on, we’ve implemented an active check 
			instead to avoid the situation where a mutex is left locked by accident and access to it by any other 
			task is therefore impossible from that point on. That is, at each system tick (as in TIMER_EXPIRED 
			kernel request), RTOS actively check whether any locked mutex has missed its deadline to be unlocked. 
			If so, an RTOS runtime error is generated and results in OS_Abort(). By doing active check, one scenario of 
			deadlock is prevented where two tasks, B and C, each holds a lock on a different mutex, and each is 
			waiting to get a lock on the other mutex. At least, a mutex timing violation is generated as an alert 
			rather than a deadlock. 
			<br>
			<br>
			<h5>Locking / Unlocking of Different Mutexes by the Same BRR Task</h5>
			Care must be taken when the same BRR task holds locks on two different mutexes and unlocks one after 
			the other. Since the BRR task has been promoted to the System level after obtaining lock on the first 
			mutex, when the first unlock is executed and one tries to restore the BRR task to its ‘original’ 
			scheduling level, the BRR task might end up being restored with the System scheduling level!
			<br>
			<br>
			<h5>Barging</h5>
			When unlocking/freeing a mutex, one shall avoid barging so that fairness and first-come-first-serve of 
			the access to mutex is asserted. Barging may occur “between the time when thread p becomes ready and 
			before it is actually running, another thread q may call mutex lock and discover it unlocked, thus 
			lock it before p.” [Extracted from the <i>Real Time Programming Concepts</i> by Dr. Mantis Cheng] To avoid 
			barging, we do not ‘unlock’ a mutex when it should become free. Instead, without unlocking the mutex, 
			the ownership is switched to the task waiting the longest on the mutex, the new owner is promoted to 
			the System level, and appended to the System task queue.
			<br>
			<br>
			<h5>Priority Inversion Problem</h5>
			To address the priority inversion problem, the RTOS specification requires that the owning BRR task of 
			a mutex is temporarily promoted to run at System level during the time it holds lock on the mutex, 
			it must free the mutex before the deadline, and it is preempted the moment it frees the mutex by 
			the new owning System task.
			<br>
			<br>
		</p>
		
	</div>
	<div id="colTwo">
		<h3>Project Sections</h3>
		<ul>
			<li class="first"><a href="part1_brr.html">Bounded Round Robin</a></li>
			<li><a href="part2_mutex.html"><b>Timed Mutex</b></a></li>
			<li><a href="part3_test_cases.html">Test Cases</a></li>
			<li><a href="part4_logic_analyzer.html">Logic Analyzer</a></li>
			<li><a href="doxygen/html/index.html">Doxygen</a></li>
			<li><a href="http://code.google.com/p/wireless-roomba">Google Code</a></li>
		</ul>
	</div>
</div>
<div id="footer">
	<p>
		@ 2009. All Rights Reserved. Design by 
		<a href="http://www.freecsstemplates.org/">Free CSS Templates</a>.
	</p>
</div>
</body>
</html>
